package edu.iastate.cs228.hw3;

import java.util.AbstractSequentialList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 * A doubly linked list that stores data in Nodes with varying size arrays as
 * the backing store.
 * 
 * Important Note: Your index-based methods remove(int pos), add(int pos, E
 * item) and listIterator(int pos) must not traverse every element in order to
 * find the node and offset for a given index pos (see spec for more details)
 * 
 * 
 * @author Devon Eilers
 * 
 */
public class DoublingList<E> extends AbstractSequentialList<E> 
{

	/**
	 * Node to keep track of the head (beginning of the list)
	 */
	private Node head;
	/**
	 * Node to keep track of the tail (end of the list)
	 */
	private Node tail;
	
	/**
	 * Total number of elements in the list
	 */
	private int size;
	
	/**
	 * Total storage capacity of the current list
	 */
	private int cap;
	
	/**
	 * Size of the array in the rightmost node
	 */
	private int curArraySize;
	/**
	 * Total number of nodes
	 */
	private int nodeCount;
	
	/**
	 * Constructs an empty DoublingList
	 */
	public DoublingList()
	{
		head = new Node(null, null, null);
		tail = new Node(null, null, null);
		
		head.next = tail;
		head.prev = null;
		
		tail.prev = head;
		tail.next = null;
		
		size = 0;
		cap = 0;
		nodeCount = 0;
		curArraySize = 0;
	}
	
	/**
	 * Copies the passed in list into this instance's list
	 * @param list
	 * 	- The list to be copied
	 */
	private void copyList(DoublingList<E> list)
	{
		this.head = list.head;
		this.tail = list.tail;
		this.size = list.size;
		this.cap = list.cap;
		this.nodeCount = list.nodeCount;
		this.curArraySize = list.curArraySize;
	}
	
	
	/**
	 * Removes the element with the given logical position, following the rules
	 * for removing an element. 
	 * 1. Find the node r and the offset j for element with logical index i. 
	 * 2. Save the contents of entry j of the array at r in a variable x and set the entry to null. 
	 * 3. If the total number of elements in L drops to zero, replace L with an empty list and return x 
	 * 4. Shift all the elements in r with offset greater than j down by one. Make
	 *    sure that the resulting empty slot in the array is set to null. See Figure 9. 
	 * 5. If L.size() <= 2^(k-2) - 1, replace L by another doubling list L' such that 
	 * 		- L' has k-1 nodes (numbered 0 through k-2), 
	 * 		- L' contains the same elements as L, in the same order, and 
	 * 		- all elements of L' are stored in nodes 0 through k-3. Thus, the last node is completely empty 
	 * 6. Return x.
	 */
	@Override
	public E remove(int pos) 
	{
		if (size==0 || pos < 0 || pos >= size)
			throw new IndexOutOfBoundsException();
		
		NodeInfo cur = find(pos);
		E toRemove = cur.node.data[cur.offset];
		if (cur.offset < cur.node.numElements-1)
		{
			if (cur.node.numElements < cur.node.data.length)
			{
				for (int i = cur.offset; i < cur.node.numElements; ++i)
				{
					cur.node.data[i] = cur.node.data[i+1];
				}
			}
			else
			{
				for (int i = cur.offset; i < cur.node.numElements-1; ++i)
				{
					cur.node.data[i] = cur.node.data[i+1];
				}
				cur.node.data[cur.node.numElements-1] = null;
			}	
		}
		else // element to be removed is at the end of the node (no shifting)
		{
			cur.node.data[cur.offset] = null;
		}
		cur.node.numElements--;
		size--;
		compactList();
		return toRemove;
	}
	
	/**
	 * Sets the size parameter for this list (for TA testing purposes only)
	 * @param size
	 * 	- the new size
	 */
	public void setSize(int size)
	{
		this.size = size;
	}
	/**
	 * Adds the given item to have the given logical position. Adds a new Node
	 * if necessary. Follows the rules stated by leftward and rightward shift.
	 * 
	 * Leftward shift at i. Let t be the rightmost predecessor of r that has
	 * empty slots (we assume that such a node exists). Then, we shift by one
	 * position to the left all elements with logical index less than or equal
	 * to i stored in the nodes between the successor of t and r inclusive. See
	 * Figure 5.
	 * 
	 * Rightward shift at i. Let t be the leftmost successor of r that has empty
	 * slots (we assume that such a node exists). Then, we shift by one position
	 * to the right every element with logical
	 */
	@Override
	public void add(int pos, E item) 
	{
		if (pos < 0 || pos > size)
			throw new IndexOutOfBoundsException();
		if (item==null)
			throw new NullPointerException();
		
		if (size==0)
		{
			addNewNodeWithItem(item);
			return;
		}
		
		NodeInfo cur = find(pos); // grabs node and offset of the given position
		
		if (cur.node==tail && cap==size) // adding to end of full list with all slots taken
		{
			addNewNodeWithItem(item);
		}
		else if (pos==0 && predHasSpace(cur.node))
		{
			NodeInfo emptySpace = predWithEmpty(cur.node);
			
			emptySpace.node.data[emptySpace.offset] = item;
			emptySpace.node.numElements++;
			size++;
		}
		else if (cur.offset==cur.node.numElements && cur.node.numElements < cur.node.data.length) // if IS at the end of the elements in this node but data array is NOT full
		{
			cur.node.data[cur.offset] = item;
			cur.node.numElements++;
			size++;
		}
		else if (cur.offset < cur.node.numElements && cur.node.numElements < cur.node.data.length) // IS NOT at end of elements in this node, and the data array is NOT full
		{
			E curItem = cur.node.data[cur.offset];
			for (int i = cur.offset+1; i <= cur.node.numElements; ++i)
			{
				E temp = cur.node.data[i];
				cur.node.data[i] = curItem;
				curItem = temp;
			}
			
			cur.node.data[cur.offset] = item;
			cur.node.numElements++;
			size++;
		}
		else if (cur.node.next == tail && cur.offset < cur.node.numElements && cur.node.numElements == cur.node.data.length && !predHasSpace(cur.node)) // IS NOT at end of elements in this node, no space in preds, and in last node before tail
		{
			E curItem = cur.node.data[cur.offset];
			for (int i = cur.offset+1; i < cur.node.numElements; ++i)
			{
				E temp = cur.node.data[i];
				cur.node.data[i] = curItem;
				curItem = temp;
			}
			cur.node.data[cur.offset] = item;
			addNewNodeWithItem(curItem);
		}
		else if (cur.node.data.length == cur.node.numElements && cur.offset != 0 && predHasSpace(cur.node)) // trying to add to the end of a full node and a predecessor has space
		{
			NodeInfo toshift = new NodeInfo(cur.node, cur.offset-1);
			NodeInfo emptySlot = predWithEmpty(cur.node);
			E curItem = cur.node.data[cur.offset];
			
			while (toshift.node != emptySlot.node)
			{
				if (toshift.offset == 0 && toshift.node.prev != emptySlot.node) // at first slot of node and previous element does not have the empty spot
				{
					// TODO mistake is in here. Edit: fuck, out of time...
					toshift.offset = toshift.node.numElements-1;
					E temp = toshift.node.data[toshift.offset];
					toshift.node.data[toshift.offset] = curItem;
					toshift.node = toshift.node.prev;
					toshift.offset = 0;
					curItem = temp;
				}
				else if (toshift.offset == 0 && toshift.node.prev == emptySlot.node) // is right before the node with empty slot
				{
					toshift.node = toshift.node.prev;
					toshift.offset = toshift.node.numElements;
					toshift.node.data[toshift.offset] = curItem;
					toshift.node.numElements++;
				}
				else
				{
					E temp = toshift.node.data[toshift.offset];
					toshift.node.data[toshift.offset] = curItem;
					toshift.offset--;
					curItem = temp;
				}
			}
			cur.node.data[cur.offset] = item;
			size++;
		}
		else if (cur.offset < cur.node.numElements-1 && cur.node.numElements == cur.node.data.length && !predHasSpace(cur.node) && succHasSpace(cur.node)) // IS NOT at the end of elements in this node, no space in preds, and a successor node has space
		{
			NodeInfo toshift = new NodeInfo(cur.node, cur.offset+1);
			NodeInfo emptySlot = succWithEmpty(cur.node);
			E curItem = cur.node.data[cur.offset];
			
			while (toshift.node != emptySlot.node)
			{
				if (toshift.offset == toshift.node.numElements-1 && toshift.node.next != emptySlot.node)
				{
					toshift.node = toshift.node.next;
					toshift.offset = 0;
					E temp = toshift.node.data[toshift.offset];
					toshift.node.data[toshift.offset] = curItem;
					toshift.offset++;
					curItem = temp;
				}
				else if (toshift.offset == toshift.node.numElements-1 && toshift.node.next == emptySlot.node)
				{
					toshift.node = toshift.node.next;
					toshift.offset = 0;
					for (int i = toshift.offset; i <= toshift.node.numElements; ++i)
					{
						E temp = toshift.node.data[i];
						toshift.node.data[i] = curItem;
						curItem = temp;
					}
				}
				else // normal shift
				{
					E temp = toshift.node.data[toshift.offset];
					toshift.node.data[toshift.offset] = curItem;
					toshift.offset++;
					curItem = temp;
				}
			}
			cur.node.data[cur.offset] = item;
			size++;
		}
		compactList();
	}


	
	/**
	 * Adds the given item to the end of the list. Creates a new Node if
	 * Necessary. Throws a NullPointerException if the item is null. Return true
	 * if the add was successful, false otherwise.
	 */
	@Override
	public boolean add(E item) 
	{
		add (size, item);
		return true;
	}
	/**
	 * Adds a new node to a linked list
	 */
	private void link (Node current, Node toAdd)
	{
		toAdd.prev = current;
		toAdd.next = current.next;
		current.next.prev = toAdd;
		current.next = toAdd;
	}
	

		
	/**
	 * Returns a ListIterator for this DoublingList at the given position (I.E.
	 * a call to next should return the element with the logical index equal to
	 * the index given)
	 */
	@Override
	public ListIterator<E> listIterator(int index) 
	{
		return new DoublingListIterator(index);
	}

	/**
	 * Returns a ListIterator for this DoublingList starting from the beginning
	 */
	@Override
	public ListIterator<E> listIterator() 
	{
		return new DoublingListIterator(0);
	}

	/**
	 * Returns an Iterator for this DoublingList starting from the beginning
	 */
	@Override
	public Iterator<E> iterator() 
	{
		return new DoublingIterator();
	}

	/**
	 * Returns the size of the list. It is acceptable to create an instance
	 * variable and update it during add / remove so you can just return that
	 * variable here.
	 */
	@Override
	public int size() 
	{
		return size;
	}

	/**
	 * Adds a new node to the doubling list and inserts the given item to the beginning of that node
	 * @param item
	 * 	- The item to be inserted
	 * @return
	 * 	- The node that was just added, including the item
	 */
	private Node addNewNodeWithItem(E item) // *TESTED* ALLOWS null elements, in case of compaction
	{
		
		curArraySize = (curArraySize==0) ? 1 : curArraySize * 2;
		
		cap += curArraySize; // increase capacity
		Node temp = new Node((E[]) new Object[curArraySize]);
		temp.data[0] = item;
		temp.numElements = (item==null) ? 0 : 1;
		link (tail.prev, temp);
		size = (item==null) ? size : size+1;
		nodeCount++;
		return temp;
	}
	
	/**
	 * Finds the node and offset of the given logical indes
	 * @param pos
	 * 	- the logical index
	 * @return
	 * 	- the NodeInfo object
	 */
	private NodeInfo find(int pos)
	{
		if (pos == -1) return new NodeInfo(head, 0);
		if (pos == size && size > 0 && tail.prev.numElements == tail.prev.data.length)
			return new NodeInfo (tail, 0);
		if (pos == size && size==0)
			return new NodeInfo (tail,0);
		
		else if (pos == size && tail.prev.numElements < tail.prev.data.length)
			return new NodeInfo(tail.prev, tail.prev.numElements);
			
		
		NodeInfo info = new NodeInfo(head.next, 0);
		int count = 0;
		int prevCount = 0;
		while (count <= pos)
		{
			prevCount = count;
			count += info.node.numElements;
			info.node = info.node.next;
		}
		info.offset = pos - prevCount;
		info.node = info.node.prev;
		
		return info;
	}
	
	/**
	 * if there are too many empty slots, creates a new list with the same elements with fewer empty spaces
	 */
	private boolean compactList()
	{
		if (size <= (Math.pow(2, nodeCount-2)-1))
		{
			DoublingList<E> temp = new DoublingList<E>();
			ListIterator<E> iter = this.listIterator();
			
			E item; 
			for (int i = 0; i < size; ++i)
			{
				item = iter.next();
				temp.add(item);
			}
			
			copyList(temp);
			addNewNodeWithItem(null);
			return true;
		}
		return false;
	}
	
	/**
	 * Returns true if a node's predecessor has empty space, false otherwise
	 */
	private boolean predHasSpace(Node cur)
	{
		Node temp = cur; // So cur's references don't get changed
		temp = temp.prev;
		while (temp != head)
		{
			if (temp.numElements < temp.data.length)
			{
				return true;
			}
			temp = temp.prev;
		}
		return false;
	}
	/**
	 * Checks to see if a successor node has available space
	 * @param cur
	 * 	- current node
	 * @return
	 * 	- true if there is space, false otherwise
	 */
	private boolean succHasSpace (Node cur)
	{
		Node temp = cur;
		temp = temp.next;
		while (temp != tail)
		{
			if (temp.numElements < temp.data.length)
			{
				return true;
			}
			temp = temp.next;
		}
		return false;
	}
	
	/**
	 * Finds the node and offset of the first empty space to the right of the node being passed in
	 * @param cur
	 * 	- The node to look to the right of
	 * @return
	 * 	- A NodeInfo object holding that node and offset
	 */
	private NodeInfo succWithEmpty (Node cur)
	{
		Node temp = cur;
		temp = temp.next;
		while (temp != tail)
		{
			if (temp.numElements < temp.data.length)
			{
				return new NodeInfo (temp, temp.numElements);
			}
			temp = temp.next;
		}
		return null;
	}
	
	
	/**
	 * Returns the rightmost predecessor that has empty space, and the first available slot in that node
	 */
	private NodeInfo predWithEmpty (Node cur)
	{
		Node temp = cur; // So cur's references don't get changed
		temp = temp.prev;
		while (temp != head)
		{
			if (temp.numElements < temp.data.length)
			{
				return new NodeInfo(temp, temp.numElements);
			}
			temp = temp.prev;
		}
		return null;
	}
	
	/**
	 * 
	 * ListIterator class. Please reference the ListIterator API to see how
	 * methods handle errors (no next element, null arguments, etc.)
	 * 
	 * API: http://docs.oracle.com/javase/6/docs/api/java/util/ListIterator.html
	 * 
	 * @param <E>
	 *            The type of elements the ListIterator will be iterating over
	 */
	private class DoublingListIterator implements ListIterator<E> 
	{
		private static final int BEHIND = -1;
	    private static final int AHEAD = 1;
	    private static final int NONE = 0;
		
		private E nextItem;
		private int index;
		private NodeInfo info;
		private int direction;
		
		public DoublingListIterator(int pos) 
		{
			if (pos < 0 || pos > size) throw new IndexOutOfBoundsException("" + index);
			
			info = find(pos);
			index = pos;
			direction = NONE;
			if (info.node == tail)
			{
				nextItem = null;
			}
			else
			{
				nextItem = info.node.data[info.offset];
			}
			
		}

		/**
		 * Adds the given element to the DoublingList following the rules of
		 * add(). DO NOT call the add method you wrote for DoublingList above!
		 * This one needs to run in O(1) (constant time).
		 */
		@Override
		public void add(E item) 
		{
			if (item==null)
				throw new NullPointerException();
//			if (direction==NONE)
//				throw new IllegalStateException();
			
			if (size==0)
			{				
				info = new NodeInfo(addNewNodeWithItem(item), 1);
			}
			else if (!hasNext() && size==cap && size > 0) // at end of list and no empty space, adds a new node *TESTED*
			{
				info = new NodeInfo(addNewNodeWithItem(item), 1);
			}			
			else if(info.node != tail && (info.node.numElements==info.offset) && (info.node.numElements < info.node.data.length)) // if IS at the end of the elements in this node but data array is NOT full *TESTED*
			{

				info.node.data[info.offset] = item;
				info.offset++;
				info.node.numElements++;
				size++;
			}
			else if (info.node==tail && !predHasSpace(info.node)) // if next() is pointing at the tail *TESTED*
			{
				NodeInfo prevNode = new NodeInfo(info.node.prev, info.node.prev.numElements);
				if (prevNode.offset < prevNode.node.data.length)
				{
					prevNode.node.data[prevNode.offset] = item;
					prevNode.node.numElements++;
					size++;
				}
				else
				{
					info = new NodeInfo(addNewNodeWithItem(item), 1);
				}
				
			}
			
			else if (info.node==tail && predHasSpace(info.node) && info.node.prev.numElements > 0)
			{
				NodeInfo prevNode = new NodeInfo(info.node.prev, info.node.prev.numElements-1);
				NodeInfo emptySlot = predWithEmpty(info.node);
				E curItem = prevNode.node.data[prevNode.offset];
				
				while (prevNode.node != emptySlot.node)
				{
					if (prevNode.offset == 0 && prevNode.node.prev != emptySlot.node)
					{
						prevNode.node = prevNode.node.prev;
						prevNode.offset = prevNode.node.data.length-1;
						E temp = prevNode.node.data[prevNode.offset];
						prevNode.node.data[prevNode.offset] = curItem;
						curItem = temp;
					}
					else if (prevNode.offset == 0 && prevNode.node.prev == emptySlot.node)
					{
						prevNode.node = prevNode.node.prev;
						prevNode.offset = prevNode.node.numElements;
						prevNode.node.data[prevNode.offset] = curItem;
						prevNode.node.numElements++;
						// the method should end here
					}
					else
					{
						E temp = prevNode.node.data[prevNode.offset-1];
						prevNode.node.data[prevNode.offset-1] = curItem;
						prevNode.offset--;
						curItem = temp;
					}
				}
				info.node.prev.data[info.node.prev.numElements-1] = item;
				size++;
			}
			else if (info.node==tail && predHasSpace(info.node) && info.node.prev.numElements == 0)
			{
				Node nPrev = info.node.prev;
				nPrev.data[0] = item;
				nPrev.numElements++;
			}
			else if ((info.offset < info.node.numElements) && (info.node.numElements < info.node.data.length)) // IS NOT at end of elements in this node, and the data array is NOT full *TESTED*
			{
				E curItem = info.node.data[info.offset];
				nextItem = curItem; // curItem must be updated due to the rightward shift
				for (int i = info.offset; i < info.node.numElements; ++i)
				{
					E temp = info.node.data[i+1];
					info.node.data[i+1] = curItem;
					curItem = temp;
				}
				
				info.node.data[info.offset] = item;
				info.node.numElements++;
				info.offset++;
				size++;
			}
			else if ((info.offset < info.node.numElements) && (info.node.numElements == info.node.data.length) && !predHasSpace(info.node) && info.node.next==tail) // IS NOT at end of elements in this node, no space in preds, and in last node before tail
			{
				E curItem = info.node.data[info.offset];
				nextItem = curItem;
				for (int i = info.offset; i < info.node.numElements-1; ++i)
				{
					E temp = info.node.data[i+1];
					info.node.data[i+1] = curItem;
					curItem = temp;
				}
				info.node.data[info.offset] = item;
				info.offset++;
				addNewNodeWithItem(curItem);
				
			}
			else if ((info.node.numElements == info.node.data.length) && predHasSpace(info.node)) // trying to add to the end of a full node and a predecessor has space
			{
				NodeInfo firstSlot = predWithEmpty(info.node); // finds nodeinfo for the first available empty slot and node
				NodeInfo toshift = new NodeInfo(info.node, info.offset-1); // where to start shifting
				E curItem = toshift.node.data[toshift.offset];
				while (toshift.node != firstSlot.node) // stop once the node with empty slots has been found
				{
					
					
					if (toshift.offset==0 && toshift.node.prev != firstSlot.node) // if at the first offset of node, and the node before does not have the empty slot
					{
						toshift.node = toshift.node.prev;
						toshift.offset = toshift.node.data.length-1;
						E temp = toshift.node.data[toshift.offset];
						toshift.node.data[toshift.offset] = curItem;
						curItem = temp;
						
					}
					else if (toshift.offset==0 && toshift.node.prev == firstSlot.node) // at first offset of node, and node before HAS empty slot
					{
						toshift.node = toshift.node.prev;
						toshift.offset = toshift.node.numElements;
						toshift.node.data[toshift.offset] = curItem;
						toshift.node.numElements++;
						// the method should end here
					}
					else // normal shift
					{
						E temp = toshift.node.data[toshift.offset-1];
						toshift.node.data[toshift.offset-1] = curItem;
						toshift.offset--;
						curItem = temp;
					}
					
				}
				info.node.data[info.offset-1] = item; // places the item in the new empty slot
				size++;
			}
			else if ((info.offset < info.node.numElements) && (info.node.numElements == info.node.data.length) && !predHasSpace(info.node) && succHasSpace(info.node)) // IS NOT at the end of elements in this node, no space in preds, and a successor node has space
			{
				NodeInfo firstSlot = succWithEmpty(info.node);
				NodeInfo toshift = new NodeInfo(info.node, info.offset);
				E curItem = toshift.node.data[toshift.offset];
				while (toshift.node != firstSlot.node)
				{
					if (toshift.offset == toshift.node.numElements-1 && toshift.node.next != firstSlot.node)
					{
						toshift.node = toshift.node.next;
						toshift.offset = 0;
						E temp = toshift.node.data[toshift.offset];
						toshift.node.data[toshift.offset] = curItem;
						curItem = temp;
					}
					else if (toshift.offset == toshift.node.numElements-1 && toshift.node.next == firstSlot.node)
					{
						toshift.node = toshift.node.next;
						toshift.offset = 0;
						E temp = toshift.node.data[toshift.offset];
						
						for (int i = toshift.offset; i <= toshift.node.numElements; ++i)
						{
							toshift.node.data[i] = curItem;
							curItem = temp;
							
							temp = toshift.node.data[i+1];
						}
						
					}
					else // normal shift
					{
						E temp = toshift.node.data[toshift.offset+1];
						toshift.node.data[toshift.offset+1] = curItem;
						toshift.offset++;
						curItem = temp;
					}
				}
				info.node.data[info.offset] = item;
				if (info.offset==info.node.data.length-1)
				{
					info.node = info.node.next;
					info.offset = 0;
					info.node.numElements++;
				}
				else
				{
					info.offset++;
					toshift.node.numElements++;
				}
				size++;
			}
			direction = NONE;
			index++;
			compactList();
		}


		/**
		 * Returns true if this list iterator has more elements when traversing
		 * the list in the forward direction. (In other words, returns true if
		 * next would return an element rather than throwing an exception.)
		 */
		@Override
		public boolean hasNext() 
		{
			return index < size;
		}

		/**
		 * Returns true if this list iterator has more elements when traversing
		 * the list in the reverse direction. (In other words, returns true if
		 * previous would return an element rather than throwing an exception.)
		 */
		@Override
		public boolean hasPrevious() 
		{
			return index > 0;
		}

		/**
		 * Returns the next element in the list. This method may be called
		 * repeatedly to iterate through the list, or intermixed with calls to
		 * previous to go back and forth. (Note that alternating calls to next
		 * and previous will return the same element repeatedly.)
		 */
		@Override
		public E next() 
		{
			
			if (!hasNext()) throw new NoSuchElementException();
			
			E ret = nextItem;
			
			if (info.offset==info.node.numElements-1 && info.node.next != tail && info.node.next.numElements != 0)
			{
				info.node = info.node.next;
				info.offset = 0;
				nextItem = info.node.data[info.offset];
			}
			else if (info.offset==info.node.numElements-1 && info.node.next != tail && info.node.next.numElements == 0) // next node is empty, skip that shit
			{
				info.node = info.node.next.next; // skips ahead of empty node
				info.offset = 0;
				if (info.node==tail)
				{
					nextItem = null;
				}
				else
				{
					nextItem = info.node.data[info.offset];
				}
				
			}
			else if (info.offset==info.node.numElements-1 && info.node.next == tail)
			{
				info.node = info.node.next;
				info.offset = 0;
				nextItem = null;
			}
			else
			{
				info.offset++;
				nextItem = info.node.data[info.offset];
			}
			index++;
			direction = BEHIND;
			return ret;
		}

		/**
		 * Returns the index of the element that would be returned by a
		 * subsequent call to next. (Returns list size if the list iterator is
		 * at the end of the list.)
		 */
		@Override
		public int nextIndex() 
		{
			return index;
		}

		/**
		 * Returns the index of the element that would be returned by a
		 * subsequent call to previous. (Returns -1 if the list iterator is at
		 * the beginning of the list.)
		 */
		@Override
		public int previousIndex() 
		{
			return index-1;
		}
		
		/**
		 * Returns the previous element in the list. This method may be called
		 * repeatedly to iterate through the list backwards, or intermixed with
		 * calls to next to go back and forth. (Note that alternating calls to
		 * next and previous will return the same element repeatedly.)
		 */
		@Override
		public E previous() 
		{
			if (!hasPrevious()) throw new NoSuchElementException();
			
			if (info.offset==0)
			{
				info.node = info.node.prev;
				info.offset = info.node.numElements-1;
				nextItem = info.node.data[info.offset];

			}
			else
			{
				info.offset--;
				nextItem = info.node.data[info.offset];
			}
			index--;
			direction = AHEAD;
			return nextItem;
		}


		/**
		 * Removes from the list the last element that was returned by next or
		 * previous (optional operation). This call can only be made once per
		 * call to next or previous. It can be made only if ListIterator.add has
		 * not been called after the last call to next or previous. DO NOT call
		 * the remove method you wrote for DoublingList above! This one should
		 * run in O(1) (constant time)
		 */
		@Override
		public void remove() 
		{
			if (direction==NONE)
				throw new IllegalStateException();
			else if (direction==BEHIND)
			{
				if (info.offset != 0 && info.offset < info.node.numElements) // is not at the end of data array (shifting required)
				{
					info.node.data[info.offset-1] = null; // clear this array element
					E curItem;
					for (int i = info.offset; i < info.node.numElements; ++i)
					{
						curItem = info.node.data[i];
						info.node.data[i-1] = curItem;						
					}
					info.node.numElements--;
					info.node.data[info.node.numElements] = null;
					info.offset--;
					
				}
				else if (info.offset == 0 && info.node.prev != head) // node to remove is in the previous node
				{
					NodeInfo toRemove = new NodeInfo(info.node.prev, info.node.prev.numElements-1);
					toRemove.node.data[toRemove.offset] = null;
					toRemove.offset--;
					toRemove.node.numElements--;
				}
				

				index--;
			}
			else // direction is AHEAD
			{
				if (info.offset != info.node.numElements-1)
				{
					info.node.data[info.offset] = null;
					E curItem;
					for (int i = info.offset+1; i < info.node.numElements; ++i)
					{
						curItem = info.node.data[i];
						info.node.data[i-1] = curItem;
					}
					info.node.numElements--;
					info.node.data[info.node.numElements] = null;
				}
				else if (info.offset==0 && info.node.numElements==1)
				{
					info.node.data[info.offset] = null;
					info.node.numElements--;
				}
				else
				{
					info.node.numElements--;
					info.node.data[info.node.numElements] = null;
				}
				
			}
			
			
			direction = NONE;
			size--;
			if (compactList()) // this method runs in an amortized O(1) time
			{
				info = find(index);
			}

		}

		/**
		 * Replaces the last element returned by next or previous with the
		 * specified element (optional operation). This call can be made only if
		 * neither ListIterator.remove nor ListIterator.add have been called
		 * after the last call to next or previous.
		 */
		@Override
		public void set(E item) 
		{
			if (direction==NONE)
				throw new IllegalStateException();
			
			if (direction==BEHIND)
			{
				NodeInfo toSet = find(index-1);
				toSet.node.data[toSet.offset] = item;
			}
			else
			{
				NodeInfo toSet = find(index);
				toSet.node.data[toSet.offset] = item;
			}
		}

	}

	/**
	 * 
	 * Iterator to be used for traversing a DoublingList. This iterator is
	 * optional if you fully implement the ListIterator but is easier and
	 * partial point will be awarded if the one is correct and your ListIterator
	 * is wrong.
	 * 
	 * API: http://docs.oracle.com/javase/6/docs/api/java/util/Iterator.html
	 * 
	 * @param <E>
	 *            The type of element to be traversed
	 */
	private class DoublingIterator implements Iterator<E> {
		
		private Node cursor;
		private NodeInfo info;
		int index;
		
		public DoublingIterator()
		{
			cursor = head.next;			
			info = new NodeInfo(cursor, 0);
			index = 0;
		}
		
		/**
		 * Returns true if the iteration has more elements. (In other words,
		 * returns true if next would return an element rather than throwing an
		 * exception.)
		 */
		@Override
		public boolean hasNext() 
		{
			return index < size;			
		}

		/**
		 * Returns the next element in the iteration.
		 */
		@Override
		public E next() // finished.. but needs testing
		{
			if (!hasNext()) throw new NoSuchElementException();
			
			if (info.offset==(cursor.data.length-1))
			{
				E retData = cursor.data[info.offset];
				cursor = cursor.next;
				
				info = new NodeInfo(cursor, 0);
				
				return retData;
			}
			else
			{
				E retData = cursor.data[info.offset];
				info.offset++;
				return retData;
			}
		}

		/**
		 * You do not need to implement this method
		 */
		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	/**
	 * Node class that makes up a DoublingList. Feel free to add methods /
	 * constructors / variables you might find useful in here.
	 * 
	 */
	private class Node 
	{
		public Node next;
		public Node prev;
		public E[] data;
		public int numElements;
		public Node(Node next, Node prev, E[] data) 
		{
			this.next = next;
			this.prev = prev;
			this.data = data;
			numElements = 0;
		}

		
		
		public Node(E[] data) 
		{
			this.data = data;
			numElements = 0;
		}

	}

	/**
	 * NodeInfo class that you may find useful to use. Again, feel free to add
	 * methods / constructors / variables that you find useful in here.
	 * 
	 */
	private class NodeInfo 
	{
		public Node node;
		public int offset;

		public NodeInfo(Node node, int offset) 
		{
			this.node = node;
			this.offset = offset;
		}
		

	}

	/**
	 * Returns a string representation of this list showing the internal
	 * structure of the nodes.
	 */
	public String toStringInternal() {
		return toStringInternal(null);
	}

	/**
	 * Returns a string representation of this list showing the internal
	 * structure of the nodes and the position of the iterator.
	 * 
	 * @param iter
	 *            an iterator for this list
	 */
	public String toStringInternal(ListIterator<E> iter) {
		int count = 0;
		int position = -1;
		if (iter != null) {
			position = iter.nextIndex();
		}

		StringBuilder sb = new StringBuilder();
		sb.append('[');
		Node current = head.next;
		while (current != tail) {
			sb.append('(');
			E data = current.data[0];
			if (data == null) {
				sb.append("-");
			} else {
				if (position == count) {
					sb.append("| ");
					position = -1;
				}
				sb.append(data.toString());
				++count;
			}

			for (int i = 1; i < current.data.length; ++i) {
				sb.append(", ");
				data = current.data[i];
				if (data == null) {
					sb.append("-");
				} else {
					if (position == count) {
						sb.append("| ");
						position = -1;
					}
					sb.append(data.toString());
					++count;

					// iterator at end
					if (position == size() && count == size()) {
						sb.append(" |");
						position = -1;
					}
				}
			}
			sb.append(')');
			current = current.next;
			if (current != tail)
				sb.append(", ");
		}
		sb.append("]");
		return sb.toString();
	}

}
